import java.util.ArrayList;
import java.util.List;

public class Solution143 {
    public void reorderList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        ListNode p = head;
        while (p != null) {
            list.add(p);
            p = p.next;
        }
        p = head;
        int n = list.size();
        for (int i = n - 1; i > n / 2; i--) {
            ListNode t = list.get(i);
            t.next = p.next;
            p.next = t;
            p = t.next;
        }
        list.get(n / 2).next = null;
    }

    void swap(ListNode a, ListNode b) {
        int t = a.val;
        a.val = b.val;
        b.val = t;
    }
}
